package stack;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @Description 剑指 Offer II 038. 每日温度  https://leetcode.cn/problems/iIQa4I/
 * @Author Firenut
 * @Date 2023-02-21 23:08
 */
public class T038_dailyTemperatures {
    // 法2: 单调栈 (也即从栈底到栈顶的元素的温度值是递减的)
    // 时间复杂度: O(n) 遍历一次temperatures数组,每个元素最多只会有一次出栈入栈的操作
    // 空间复杂度: O(n) 需要借助辅助数组 ans
    public int[] dailyTemperatures(int[] temperatures) {
        Deque<Integer> stack = new ArrayDeque<>(); //栈内存放的是下标值,使用下标值可以直接获取数组的元素
        int[] ans = new int[temperatures.length];

        for (int i = 0; i < temperatures.length; i++) {
            // 只要当前元素大于栈顶元素
            while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
                // 如果出栈后栈内还有元素并且栈顶元素值仍小于当前值，继续执行出栈操作
                int index = stack.pop(); // 出栈
                ans[index] = i - index;        // 记录
            }
            stack.push(i);  // 栈为空或者当前元素值小于栈顶元素,执行入栈操作
        }
        return ans;
    }

    // 法1: 暴力解法
    // 时间复杂度为O(n^2)
    public int[] dailyTemperatures1(int[] temperatures) {
        int []ans = new int[temperatures.length];

        for(int i=0;i<temperatures.length;i++){
            for(int j=i+1;j<temperatures.length;j++){
                if(temperatures[j]>temperatures[i]){
                    ans[i]=j-i;
                    break;
                }
            }
        }
        return ans;
    }
}
